package DataStructureAndAlgorithm.AcWing_每日一题.多源最短路;

//链接：https://www.acwing.com/problem/content/3828/
//题目类似于力扣的某一题，即如果能在半路遇到，一定能在终点遇到对方。因为，在中途遇到之后，两个人可以从相同的路径一起到达终点
//由此，题目可以转换为求各个点到终点的最短距离中，有多少个比起点到终点的最短距离还短
//题目因此变为多源最短路问题，可以用BFS，也可以通过建立超级源点，求出各个点到终点的最短距离
import java.util.*;

class AcWing_3825{

    static class pair{
        int x;
        int y;
        pair(int x,int y){
            this.x = x;
            this.y = y;
        }
    }

    static int N = 1010;
    //用来表示每个点到终点的距离
    static int[][] dist = new int[N][N];
    //用来表示四个方向
    static int[] dx = {-1,0,1,0};
    static int[] dy = {0,1,0,-1};
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int r = in.nextInt();
        int c = in.nextInt();
        String[] str = new String[r];
        for (int k = 0; k < r; k++){
            str[k] = in.next();
        }

        int myDist = bfs(str);
        int res = 0;
        for (int i = 0; i < r; i++){
            for (int j = 0; j < c; j++){
                if (str[i].charAt(j) > '0' && str[i].charAt(j) <= '9' && dist[i][j] <= myDist){
                    res += str[i].charAt(j) - '0';
                }
            }
        }
        System.out.println(res);
        in.close();
    }
    //从终点开始BFS，并放回起点到终点的最短距离
    static int bfs(String[] str){

        for (int i = 0; i < str.length; i++){
            Arrays.fill(dist[i],Integer.MAX_VALUE / 3);
        }
        //先找到终点
        int startX = 0,startY = 0;
        for (int i = 0; i < str.length; i++){
            for (int j = 0; j < str[i].length(); j++){
                if (str[i].charAt(j) == 'E'){
                    startX = i;
                    startY = j;
                }
            }
        }
        //宽搜所有点到终点的距离
        Queue<pair> queue = new LinkedList<>();
        queue.offer(new pair(startX,startY));
        dist[startX][startY] = 0;
        while (!queue.isEmpty()){
            pair temp = queue.poll();
            for (int i = 0; i < 4; i++){
                int x = temp.x + dx[i];
                int y = temp.y + dy[i];
                //如果可以走
                if (x >= 0 && x < str.length && y >= 0 && y < str[0].length() && str[x].charAt(y) != 'T'){
                    //如果路径可以更新，就更新，并入队
                    if (dist[x][y] > dist[temp.x][temp.y] + 1){
                        dist[x][y] = dist[temp.x][temp.y] + 1;
                        queue.offer(new pair(x,y));
                    }
                }

            }
        }

        //找出起点到终点的最短距离，并返回
        for (int i = 0; i < str.length; i++){
            for (int j = 0; j < str[i].length(); j++){
                if (str[i].charAt(j) == 'S'){
                    return dist[i][j];
                }
            }
        }
        //这句永远不会被执行
        return -1;
    }
}